Overdetermined system

For the philosophical term, see overdetermination.

In mathematics, a system of linear equations is considered overdetermined if there are more equations than unknowns.^[1] The terminology can be described in terms of the concept of counting constraints. Each unknown can be seen as an available degree of freedom. Each equation introduced into the system can be viewed as a constraint that restricts one degree of freedom.

Therefore the critical case occurs when the number of equations and the number of independent variables are equal. For every degree of freedom, there exists a corresponding restraint. The overdetermined case occurs when the system has been overconstrained—that is, when the number of equations outnumbers the number of the unknowns.

1 Systems of equations
- 1.1 An example in two dimensions
- 1.2 Matrix form
2 General cases
- 2.1 Homogeneous case
- 2.2 Inhomogeneous case
3 Approximate solutions
4 In general use
5 See also
6 References

Systems of equations

An example in two dimensions

Consider the system of 3 equations and 2 unknowns (x₁ and x₂):

$2x_1%2Bx_2=-1$

$-3x_1%2Bx_2=-2$

$-x_1%2Bx_2=1$

Note: equations above correspond to picture #1 such that x₁ = x and x₂ = y in the Cartesian coordinate plane

There are three "solutions" to the system as can be determined from the graph's intersections, one for each pair of linear equations: between one and two (0.2, −1.4), between one and three (−2/3, 1/3), between two and three (1.5, 2.5). However there is no solution that satisfies all three simultaneously. Systems of this variety are deemed inconsistent.

The only case where the overdetermined system does in fact have a solution is demonstrated in pictures four, five, and six. These exceptions occur when the overdetermined set contains linearly dependent equations. Linear dependence means that the elements of a set can be described in terms of existing equations. For example, y = x + 1 and 2y = 2x + 2 are linearly dependent equations.

Matrix form

Any system of linear equations can be written as a matrix equation. The previous system of equations can be written as follows:

$\begin{bmatrix} 2 & 1 \\ -3 & 1 \\ -1 & 1 \\ \end{bmatrix} \begin{bmatrix} X_1 \\ X_2 \\ \end{bmatrix} = \begin{bmatrix} -1 \\ -2 \\ 1 \\ \end{bmatrix}$

Notice that the number of rows outnumber the number of columns. In linear algebra the concepts of row space, column space and null space are important for determining the properties of matrices. The informal discussion of constraints and degrees of freedom above relate directly to these more formal concepts.

General cases

Homogeneous case

The homogeneous case is always consistent (because there is a trivial, all-zero solution). There are two cases, in rough terms: there is just the trivial solution, or the trivial solution plus an infinite set of solutions, of nature determined by the number of linearly dependent equations.

Consider the system of linear equations: L_i = 0 for 1 ≤ i ≤ M, and variables X₁, X₂, ..., X_N, then X₁ = X₂ = ... = X_N = 0 is always a solution. When M < N the system is underdetermined and there are always further solutions. In fact the dimension of the space of solutions is always at least N − M.

For M ≥ N, there may be no solution other than all values being 0. There will be other solutions just when the system of equations has enough dependencies (linearly dependent elements), so that the number of effective constraints is less than the apparent number M; more precisely the system must reduce to at most N − 1 equations. All we can be sure about is that it will reduce to at most N.

Inhomogeneous case

When studying systems of linear equations, L_i=c_i for 1 ≤ i ≤ M, in variables X₁, X₂, ..., X_N the equations L_i are sometimes linearly dependent. These dependent equations (often described in terms of vectors) lead to three possible cases for an overdetermined system.

M equations* and N unknowns*, such that M > N and all M are linearly independent. This case yields no solution.
M equations and N unknowns, such that M > N but all M are not linearly independent. There exist three possible sub-cases of this:
- M equations and N unknowns, such that M > N but all M are not linearly independent, but when the linearly dependent equations(D) are removed M - D > N. This case yields no solutions.
- M equations and N unknowns, such that M > N but all M are not linearly independent, but when the linearly dependent equations(D) are removed M - D = N. This case yields a single solution.
- M equations and N unknowns, such that M > N but all M are not linearly independent, but when the linearly dependent equations(D) are removed M - D < N. This case yields infinitely many solutions. Which can be described as F which is the entirety of the field in which the equations are operating.

Note:(*Equations and unknowns can correspond to the rows and columns of a matrix respectively)

M equations and N unknowns, such that M < N and all M are linearly dependent. This case yields infinitely many solutions except in some cases where the solution is sparse (see Compressed Sensing)

The discussion is more convincing, perhaps, when translated into the geometric language of intersecting hyperplanes. The homogeneous case applies to hyperplanes through a given point, taken as origin of coordinates. The inhomogeneous case is for general hyperplanes, which may therefore exhibit parallelism or intersect. A sequence of hyperplanes H₁, H₂, ..., H_M gives rise to intersections of the first k, which are expected to drop in dimension 1 each time. If M > N, the dimension of the ambient space, we expect the intersection to be empty, and this is precisely the overdetermined case.

Approximate solutions

The method of least squares can be used to find an approximate solution to overdetermined systems. For the system $Ax = b$ , the least squares formula can be written $x =(A'A)^{-1}A'b$ ^[2] with this formula an approximate solution is found.

$\min_{x}\Vert Ax - b \Vert$

In general use

The concept can also be applied to more general systems of equations, such as partial differential equations.

References

^ Overdetermined equations at planetmath.org
^ Howard Anton, Chris Rorres, (2005), Elementary Linear Algebra (9th ed.), John Wiley and Sons, Inc., ISBN 978-0-471-66959-3